package LinkList;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class item23 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        ListNode fakeHead = new ListNode(-1);
        Queue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {

                return o1.val- o2.val;
            }
        });
       for(ListNode head:lists)
       {
           pq.add(head);
       }
       ListNode p =fakeHead;
       while (!pq.isEmpty())
       {
           ListNode temp = pq.poll();
           p.next = temp;
           p = temp;
           if(temp.next!=null)
           {
               pq.add(temp.next);
           }
       }
        return fakeHead.next;
    }
}
